package cn.felord.boot;

public class ClimbStairs {

    /**
     * 爬楼梯问题：爬楼梯时 ，每⼀步会有两个选择：爬⼀个台阶和爬两个台阶 ，
     * 问 ：楼梯总台阶数为n ，则⼀共有多少种爬法 ，
     * 写一个函数f，使得：总的爬法= f(n)。
     * 举例： n=3时 ，则共有： （ 1,1,1)、 (1,2) 、(2,1)三种爬法 ，则f(3)=3。
     * n=1时,组合{1},f(1) = 1
     * n=2时,组合{1,2},f(2) = 2
     * n=3时,组合{1,1,1},{1,2},{2,1},f(3) = f(2) + f(1) = 3
     * n=4时,组合{1,1,1,1},{2,2},{1,1,2},{1,2,1},{2,1,1},f(4) = f(3) + f(2) = 5
     * f(n) = f(n-1) + f(n-2),n>2
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }




}
